This invention relates generally to a method for translating addresses between the addressing scheme determined by the Internet Protocol and another addressing scheme used by a data communication network.
The Internet Protocol is a widely used protocol for the transmission of data communication packets over a network of participating digital communication networks. The operation of the Internet Protocol is described in detail in Stallings, Handbook of Communication Standards vol. 3 (1990), a generally-available reference in the field, the contents of which are herein incorporated by reference. One example of a network of networks which operates according to the Internet Protocol is the Internet, a global network of networks which operates with decentralized management. Herein, all interconnected networks of networks which operate according to the Internet Protocol are referred to as internets.
FIG. 1 depicts an exemplary internet which comprises a first local area network (LAN) 2, a second LAN 4 and a long haul network 6 which allows for packets to be communicated between the LANs. Host nodes A through F and gateway node G are connected to LAN 2. Host nodes H through L and gateway node M are connected to LAN 4. Each host node and gateway node possesses a unique local network address known as a Medium Access Controller (MAC) address. The MAC address is uniquely assigned to each node and does not depend on the identity of the network to which the node is connected. LANs 2 and 4 are not limited to any specific topology but operate to allow a data communication packet to be forwarded from a source node connected to the network to any target node connected to the network provided that the MAC address of the target node is included in a header of the packet.
Long haul network 6 comprises routers H, I, J, K, and L and is also connected to gateway nodes G and M to permit packets to be communicated between LANs 2 and 4. Each node connected to LANs 2 and 4 has in addition to its MAC address a uniquely assigned Internet Protocol (IP) address which identifies the node and the network to which the node is connected. Typically, each node is aware of its own IP address and MAC address.
The internet depicted in FIG. 1 is intended to illustrate the basic architecture of an internet. An actual internet may serve to interconnect many more than two networks. Furthermore, the networks interconnected by an internet need not be LANs but may be wide area networks (WANs) or have other topologies such as mesh, ring etc.
Using the Internet Protocol, a source node connected to LAN 2 may transmit a data communication packet to a target node connected to LAN 4. Transmission of a data packet according to the Internet Protocol from source node A connected to LAN 2 to target node N connected to LAN 4 proceeds as follows. Source node A includes the IP address of target node N in a header of the packet. The packet is then transmitted over LAN 2 to gateway node G and from there it is relayed over long haul network 6 following a linked path consisting of routers, H, I, and J, eventually arriving at gateway node M connected to LAN 4. The path taken by the packet through long haul network 6 is not necessarily predetermined but rather each router may select a successor router upon receipt of the packet. The selection of successor router is made based on the IP address of the target node, network connectivity information of which the router is aware, and other parameters such as network traffic and the priority of the packet.
The packet must then be forwarded from gateway node M to target node N. Typically, the operation of an LAN requires that packets transmitted over the LAN be addressed using the MAC address and not the IP address of the target node. However, the Internet Protocol does not require that the MAC address be included in a header of the packet when it is received at gateway node M, which as herein explained can present problems.
The gateway node M may already be aware of the MAC address of host node N and may then forward the packet to host node N using the MAC address. If the gateway node M is unaware of the MAC address of the host node N it typically determines the MAC address by a method known as the Address Resolution Protocol (ARP). The ARP exploits the broadcast property of an LAN: namely, that a transmission from any node on the network is received by all other nodes on the network.
The gateway node M thus determines the MAC address of the target node N using the ARP as follows. The gateway node M broadcasts over the LAN 4 an inquiry message containing the IP address of the target node N. The target node N then responds with a reply message containing as a matched pair both its own MAC address and its own IP address. The gateway node M stores the paired MAC address and IP address in a local routing table at the gateway node M. The packet may then be forwarded to the target node N by including the MAC address in a header of the packet. Packets received at the gateway node and addressed to the IP address of the target node are henceforth forwarded using the MAC address stored in the local routing table at the gateway node.
The ARP thus allows a packet forwarded over an internet and received at a gateway node connected to a local network to be forwarded to the target node to which the packet is directed. However, only networks with certain properties may effectively use the ARP. For example, the network should have the broadcast property typically associated with LANs, that is, the network must be physically configured so that each node can directly receive an inquiry message broadcast over the network. If one or more nodes within the LAN cannot directly receive an inquiry message, further relaying of the inquiry message will be required at an increased expense in network resources. Frequent ARP inquiry messages will therefore reduce network efficiency. Larger network operation can be substantially impaired by the ARP inquiry messages.
If the network lacks the broadcast property of LANs and ARP inquiry messages may only be broadcast at high cost, the resulting network inefficiency is further compounded when the network composition is unstable and a large fraction of the nodes on the network have recently been connected. In this situation, a gateway node receiving a packet for relay to a target node connected to the network will very often lack the MAC address of the target node and will be forced to broadcast an ARP inquiry message to determine the MAC address. The expensive ARP inquiry messages will therefore be frequent and network efficiency will be substantially impaired.
Moreover, a recently connected target node will often be unaware of its own IP address, since the IP address in part depends on the identity of the participating network to which the node is connected. The target node may at different times connect and disconnect to various networks and therefore lack a stable IP address. Such a target node will be unable to reply to an ARP broadcast because it will not recognize a particular IP address as being its own.
A network which is a wireless data communication network is exemplary of networks which cannot effectively forward packets received over an internet by using the ARP to translate IP addresses to local network addresses. In such networks, nodes often cannot communicate with one another directly, and packets are typically transmitted via a series of intermediate nodes. The broadcast of an ARP inquiry message to all the nodes in the network is therefore prohibitively expensive, since it would require that an inquiry packet be relayed to each node connected to the wireless network.
The expense of broadcasting is further compounded if the wireless network consists all or in part of mobile nodes. Mobile nodes may be connected to a particular network for only a short period of time. A gateway node on a wireless network is likely to be unaware of the MAC address associated with a target node to which a packet received at the gateway node is addressed. Therefore, expensive ARP inquiry messages are likely to be very frequent. Furthermore, a mobile node may be unaware of its own IP address and thus be unable to respond to an ARP inquiry message.
A further difficulty arises in networks which use certain geographical routing methods for forwarding packets. A geographical routing method is disclosed in U.S. Pat. No. 4,939,726, which is herein incorporated by reference. In a network which makes use of the therein disclosed geographic routing method, a packet is typically forwarded from a source node to a target node via a series of intermediate nodes. The address of the target node is included in a header of the packet. The disclosed method requires that packet addresses incorporate the geographic coordinates of the target node. Each intermediate node typically selects a successor intermediate node based on the maximum forward progress attainable using the least amount of power. Forward progress is determined by calculating a metric incorporating the geographical distance between the geographic coordinates of the target node and the geographic coordinates of each node to be evaluated for selection as a successor intermediate node. The geographic coordinates of the target node are derived from the address of the target node found in the header of the packet. Thus, retrieving the MAC address of the target node, as is accomplished by the ARP, will be insufficient to relay a packet to the target node over such a network, because the MAC address does not contain any information about the geographic coordinates of the target node.
Another difficulty arises when storage at the gateway node is limited so that only a restricted number of pairings of IP addresses and network specific local addresses is retained. If the ARP method for translation is used, repeated broadcasts may be necessary as pairings are lost or overwritten.
It is desirable to send packets from a source node connected to an originating network which participates in an internet to a target node connected to a destination network which participates in the same internet where the characteristics of the destination network preclude effective use of the ARP. What is needed is a method for translating an IP address to a local network address that does not require broadcasting as a step in translation and can accommodate nodes that have recently connected to the network and require IP address assignments.
It is also desirable to send packets from a source node connected to an originating network which participates in an internet to a target node connected to a destination network which participates in the same internet and cannot use a MAC address to forward packets from a gateway node on the destination network to the target node. What is needed is a method for translating an IP address to a network specific local address which may be used to forward packets from a gateway node to a target node over a destination network which cannot use MAC addresses for forwarding packets. For example, a translation method is needed which given the IP address of a target node provides a network specific local address which incorporates the geographic coordinates of the target node.
Furthermore, it is desirable to have ample remote storage of pairings between IP address and network specific local addresses which may be accessed by any node connected to a network which participates in an internet. What is needed is a remote address server which can store pairings of IP addresses and network specific local addresses and can respond to requests forwarded over an internet for translation of IP addresses to network specific local addresses.